package zeng.glogo.learn;

import java.io.IOException;
import java.util.Arrays;
import java.util.Scanner;

/**
*
* @author B11041225
*/
public class SortableList {
   
   private int array[];       //the array
   //private int maxSize = 0;    //the maxmum size of the list
   private int n=0;            //current numbers in the array
   Scanner scanner = new Scanner(System.in);
   
   public SortableList(int maxSize) {
       //this.maxSize = maxSize;
       array = new int[maxSize];
       n = array.length;
   }
   
   /*
    *  Input the array
    */
   public void Input(){
	   System.out.println("array.length="+array.length);
       for(int i=0 ;i<array.length ; i++){
               array[i] = scanner.nextInt();         
       }    
   }
   
  /*
   *    Output the array
   */
   public void Ouput(){
      System.out.println(Arrays.toString(array));
   }
   
   /*
    * merges sort
    * the interfaces provided
    */
    public void MergeSort(){
        MergeSort(0,n-1);
    }
   
    private void MergeSort(int left, int right){
         if(left < right){
            int mid = (left + right)/2;
            MergeSort(left, mid);
            MergeSort(mid+1, right);
            MergeSort(left, mid, right);
        }
    }
    
    private void MergeSort(int left, int mid, int right){
        int temp[] = new int[right-left+1];
        int i = left, j = mid+1, k = 0;
        while((i <= mid)&&(j <= right)){
            if(array[i] <= array[j])
                temp[k++] = array[i++];
            else
                temp[k++] = array[j++];
            while(i <= mid)
                temp[k++] = array[i++];
            while(j <= right)
                temp[k++] = array[j++];
            for(i = 0 , k = left ; k <= right ;)
                array[k++] = temp[i++];
        }
    }
    
    
    /*
     *quick sort
     */
     public void QuickSort(){
        QuickSort(0,n-1);
    }
     
     private void QuickSort(int left,int right){
         if (left<right)
          {
               int j=Partition(left,right);
               QuickSort(left,j-1);
               QuickSort(j+1,right);
           }
      }
     
     private void Swap(int i, int j){
         int c = array[i];
         array[i] = array[j];
         array[j] = c;
     }
     
     private int Partition(int left,int right){
         int i = left, j = right +1;
         do{
             do i++ ;  while(array[i]<array[left]);
             do j--;   while(array[j]>array[left]);
             if (i<j)   Swap(i,j);
       }while (i<j);
       Swap(left,j);
       return j;
    }
     
     public static void main(String[] args) throws IOException{
       System.out.println("==== ==== Exam1.1 : MergeSort ==== ====");
       SortableList sl1 = new SortableList(10);
       sl1.Input();
       sl1.MergeSort();
       sl1.Ouput();
       System.out.println("==== ==== Exam1.2 : QuickSort ==== ====");
       SortableList sl2 = new SortableList(10);
       sl2.Input();
       sl2.Ouput();
   }
}